package P2分治回溯;

//插值查找
public class InterpolationSearch {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 19, 20, 22, 25, 29, 30, 35, 41, 44, 49, 58, 62};
        int key = 999;
        //迭代
//        System.out.println(interpolationSearch(arr, key));
        System.out.println(interpolationSearch(arr, 0, arr.length - 1, key));
        System.out.println(binarySearch(arr, 0, arr.length - 1, key));
    }

    private static int binarySearch(int[] arr, int low, int high, int key) {
        System.out.println("binarySearch...");
        if (low > high) {
            return -1;
        }
        int mid = (high - low) / 2 + low;
        if (arr[mid] == key) {
            return mid;
        }
        if (arr[mid] < key) {
            return binarySearch(arr, mid + 1, high, key);
        } else {
            return binarySearch(arr, low, mid - 1, key);
        }
    }

    private static int interpolationSearch(int[] arr, int low, int high, int key) {
        System.out.println("interpolationSearch...");
        if (low > high) {
            return -1;
        }
        int mid = low + (int) (1.0 * (key - arr[low]) / (arr[high] - arr[low]) * (high - low));
        if (mid < low || mid > high) {
            return -1;
        }
        if (arr[mid] == key) {
            return mid;
        }
        if (arr[mid] < key) {
            return interpolationSearch(arr, mid + 1, high, key);
        } else {
            return interpolationSearch(arr, low, mid - 1, key);
        }

    }

    private static int interpolationSearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        int mid = low + (int) (1.0 * (key - arr[low]) / (arr[high] - arr[low]) * (high - low));
        if (mid > high || mid < low) {
            return -1;
        }
        while (arr[mid] != key) {
            if (arr[mid] < key) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
            if (low > high) {
                return -1;
            }
            mid = low + (int) (1.0 * (key - arr[low]) / (arr[high] - arr[low]) * (high - low));
            if (mid > high || mid < low) {
                return -1;
            }
        }
        return mid;
    }
}
